public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {4,1,2,7,5,8,3,0,9};
        int size = arr.length;//7

        //建大堆方法一(N*logN)
        /*for(int i = 0; i < size-1 ; i++) {
            heapInsert(arr,i);
        }*/

        //建大堆方法二(N)
        for(int i = size-1; i > 0 ; i--) {
            heapify(arr,i,size);
        }


        //堆排序
        while (size > 0) {
            --size;
            swap(arr,0,size);
            heapify(arr,0,size);

        }
        //打印结果
        for(int e : arr) {
            System.out.print(e + " ");
        }
    }


    //i为 当前位置的数，向上调整建大根堆
    public static void heapInsert(int[] arr, int i) {
        while (arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    //i位当前位置，向下调整建大根堆
    //size表示数组的范围
    public static void heapify(int[] arr, int i, int size) {
        int child = (i * 2) + 1;
        while (child < size) {
            int childMax = (child + 1 < size) && arr[child + 1] > arr[child] ? child + 1 : child;
            if (arr[childMax] > arr[i]) {
                swap(arr, childMax, i);
                i = childMax;
                child = (i * 2) + 1;
            }else {
                break;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
